#!/usr/bin/env python
# encoding: utf-8
'''
@author: Excelsiorly
@license: (C) Copyright 2022, All Rights Reserved.
@contact: excelsiorly@qq.com
@file: 002. 两数相加.py
@time: 2022/1/15 14:42
@desc: https://leetcode-cn.com/problems/add-two-numbers/
> 给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

@解题思路：
    1. 没什么好说的，就硬算
    2. t: O(max(m,n)), s: O(1)
'''
# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution(object):
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        if not l1 or not l2: return None
        dummy = ListNode(-1)
        p = dummy
        up = 0
        while l1 and l2:
            s = l1.val + l2.val + up
            if s>=10:
                up = 1
                s = s%10
            else:
                up = 0
            p.next = ListNode(s)
            p = p.next
            l1 = l1.next; l2 = l2.next
        if l1:
            l1_head = l1
            while l1 and not up==0:
                s = l1.val + up
                if s>=10:
                    s = s%10
                else:
                    up = 0
                l1.val = s
                l1 = l1.next
            p.next = l1_head
        if l2:
            l2_head = l2
            while l2 and not up==0:
                s = l2.val + up
                if s>=10:
                    s = s%10
                else:
                    up = 0
                l2.val = s
                l2 = l2.next
            p.next = l2_head
        if not up==0:
            p = dummy
            while p.next:
                p = p.next
            p.next = ListNode(1)
        return dummy.next
